﻿#include "Heap.h"
void Swap(int* x, int* y) {
	int t = *x;
	*x = *y;
	*y = t;
}
void AdjustUp(int* a, int child) {
	assert(a);
	int parent = (child - 1) / 2;
	while (parent >= 0) {
		if (a[parent] < a[child]) {
			Swap(a + parent, a + child);
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}
void AdjustDown(int* a, int n, int parent) {
	assert(a);
	int child = parent * 2 + 1;
	while (child < n) {
		if (child + 1 < n && a[child] < a[child + 1]) {
			child++;
		}
		if (a[parent] < a[child]) {
			Swap(a + parent, a + child);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
void HeapInit(HP* p) {
	assert(p);
	p->a = 0;
	p->size = p->capacity = 0;
}
HP* HeapCreat(int* a, int n) {
	assert(a);
	HP* p = (HP*)malloc(sizeof(HP));
	HeapInit(p);
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	p->a = (int*)malloc(sizeof(int) * n);
	p->capacity = n;
	memcpy(p->a, a, sizeof(int) * n);
	p->size = n;
	return p;
}
void HeapPush(HP* p, int x) {
	assert(p);
	if (p->size == p->capacity) {
		p->capacity = p->capacity == 0 ? 4 : p->capacity * 2;
		p->a = (int*)realloc(p->a, sizeof(int) * p->capacity);
	}
	p->a[p->size++] = x;
	AdjustUp(p->a, p->size - 1);
}
void HeapPop(HP* p) {
	assert(p && p->a);
	if (!p->size) {
		return;
	}
	Swap(p->a, p->a + p->size - 1);
	p->size--;
	AdjustDown(p->a, p->size, 0);
}
int HeapTop(HP* p) {
	assert(p && p->a && p->size > 0);
	return p->a[0];
}
bool HeapEmpty(HP* p) {
	assert(p);
	return p->size == 0;
}
void HeapPrint(HP* p) {
	assert(p && p->a);
	for (int i = 0; i < p->size; i++) {
		fprintf(stdout, "%d ", p->a[i]);
	}
	puts("");
}
void HeapDestroy(HP* p) {
	free(p->a);
	free(p);
}
int main() {
	int a[] = { 8,7,2,3,4,1,9,6,5 };
	HP* p1 = (HP*)malloc(sizeof(HP));
	HeapInit(p1);
	for (int i = 0; i < 4; i++) {
		HeapPush(p1, i + 2);
		HeapPush(p1, i - 1);
	}
	HeapPrint(p1);

	HP* p = HeapCreat(a, sizeof(a) / sizeof(int));
	HeapPrint(p);
	int n = p->size;
	for (int i = 0; i < n; i++) {
		HeapPop(p);
		HeapPrint(p);
	}

	for (int i = 0; i < 4; i++) {
		HeapPush(p, i + 2);
		HeapPush(p, i - 1);
	}
	HeapPrint(p);

	HeapDestroy(p);
	HeapDestroy(p1);
	return 0;
}